package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/find-nearest-right-node-in-binary-tree/'>找到二叉树中最近的右侧节点(Find Nearest Right Node in Binary Tree)</a>
 * <p>给定一棵二叉树的根节点 root 和树中的一个节点 u ，返回与 u 所在层中距离最近的右侧节点，当 u 是所在层中最右侧的节点，返回 null 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * Example 1:
 *      Input: root = [1,2,3,null,4,5,6], u = 4
 *                       1
 *                    /   \
 *                   2     3
 *                    \   / \
 *                     4 5  6
 *      Output: 5
 *      Explanation: The nearest node on the same level to the right of node 4 is node 5.
 *
 * Example 2:
 *      Input: root = [3,null,4,2], u = 2
 *                      3
 *                       \
 *                        4
 *                       /
 *                      2
 *
 *      Output: null
 *      Explanation: There are no nodes to the right of 2.
 *
 * Example 3:
 *      Input: root = [1], u = 1
 *      Output: null
 *
 * Example 4:
 *      Input: root = [3,4,2,null,null,null,1], u = 4
 *      Output: 2
 * </pre>
 * </p>
 *
 * <p>
 * <b>Constraints:</b>
 * <ul>
 *     <li>The number of nodes in the tree is in the range [1, 10^5].</li>
 *     <li>1 <= Node.val <= 10^5</li>
 *     <li>All values in the tree are distinct.</li>
 *     <li>u is a node in the binary tree rooted at root.</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/4 14:38
 */
public class LC1602FindNearestRightNodeInBinaryTree_M {

    static class Solution {
        public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    if (u == currNode) {
                        // 如果是当前层最后一个节点，返回null;否则返回右侧的节点
                        if (i == currLevelNodeSize - 1) {
                            return null;
                        } else {
                            return queue.poll();
                        }
                    }
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                }
            }
            return null;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        TreeNode node4 = new TreeNode(4);
        root1.left.right = node4;
        root1.right = new TreeNode(3);
        root1.right.left = new TreeNode(5);
        root1.right.right = new TreeNode(6);
        Solution solution = new Solution();
        TreeNode.printTree(solution.findNearestRightNode(root1, node4));
    }
}
